/*
 * @FilePath: /data-and-structure-lv/15/cut-rod.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2022-01-02 10:16:16
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2022-01-02 18:02:48
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

typedef struct RAndS_Tag
{
    int *r;
    int *s;
} RAndS;

int cut_rod(int *p, int n)
{
    if (n == 0)
    {
        return 0;
    }
    int q = INT_MIN;
    for (int i = 1; i <= n; i++)
    {
        q = fmax(q, p[i] + cut_rod(p, n - i));
    }
    return q;
}

int memoized_cut_rod_aux(int *p, int n, int *r)
{
    if (r[n] >= 0)
    {
        return r[n];
    }
    int q;
    if (n == 0)
    {
        q = 0;
    }
    else
    {
        q = INT_MIN;
        for (int i = 1; i <= n; i++)
        {
            q = fmax(q, p[i] + memoized_cut_rod_aux(p, n - i, r));
        }
    }
    r[n] = q;
    return q;
}

int memoized_cut_rod(int *p, int n)
{
    int r[n];
    for (int i = 0; i <= n; i++)
    {
        r[i] = INT_MIN;
    }
    return memoized_cut_rod_aux(p, n, r);
}

int bottom_up_cut_rod(int *p, int n)
{
    int r[n];
    r[0] = 0;
    for (int j = 1; j <= n; j++)
    {
        int q = INT_MIN;
        for (int i = 1; i <= j; i++)
        {
            q = fmax(q, p[i] + r[j - i]);
        }
        r[j] = q;
    }
    return r[n];
}

RAndS *extended_bottom_up_cut_rod(int *p, int n)
{
    RAndS *rAndS = malloc(sizeof(RAndS));
    int *r = malloc(sizeof(int) * (n + 1));
    int *s = malloc(sizeof(int) * (n + 1));
    if (rAndS == NULL || r == NULL || s == NULL)
    {
        printf("malloc error\n");
        return;
    }

    r[0] = 0;
    for (int j = 1; j <= n; j++)
    {
        int q = INT_MIN;
        for (int i = 1; i <= j; i++)
        {
            if (q < p[i] + r[j - i])
            {
                q = p[i] + r[j - i];
                s[j] = i;
                r[j] = q;
            }
        }
    }
    rAndS->r = r;
    rAndS->s = s;
    return rAndS;
}

void release_r_and_s(RAndS *rAndS)
{
    free(rAndS->s);
    free(rAndS->r);
    free(rAndS);
}

print_cut_rod_solution(int *p, int n)
{
    RAndS *rAndS = extended_bottom_up_cut_rod(p, n);
    while (n > 0)
    {
        printf("%d ", rAndS->s[n]);
        n = n - rAndS->s[n];
    }
    printf("\n");
    release_r_and_s(rAndS);
}

void main()
{
    int p[] = {INT_MIN, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    int n = 4;
    int q = cut_rod(p, 4);
    printf("收益: %d\n", q);

    q = memoized_cut_rod(p, 4);
    printf("收益: %d\n", q);

    q = bottom_up_cut_rod(p, 4);
    printf("收益: %d\n", q);

    print_cut_rod_solution(p, 10);
    print_cut_rod_solution(p, 7);
}